﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution240
{
    //思路，观察发现，target右边的和下边的数都比较大
    //左边和上面的数都比它小
    //使用两个指针
    public bool SearchMatrix2(int[][] matrix, int target)
    {
        int m=matrix.Length;
        int n = matrix[0].Length;

        int top = 0;
        int bottom = m-1;
        int left = 0;
        int right = n-1;
        int colIndex = (left+right)/2;
        int rowIndex = (top + bottom) / 2;
        if (matrix[rowIndex][colIndex] > target)//一定是左上角
        {

            bottom = rowIndex-1;
            right = colIndex-1;



        }else if (matrix[rowIndex][colIndex] < target)
        {
            //三种情况判断
            //无法判断




        }else { return true; }

        return true;

    }
    //从右上角开始，左边的都比他小，下面的都比他大

    public bool SearchMatrix(int[][] matrix, int target)
    {
        int m = matrix.Length;
        int n = matrix[0].Length;
        int colIndex = n-1;
        int rowIndex = 0;

while(rowIndex < m&&colIndex>=0)
        {
            if (matrix[rowIndex][colIndex] > target)
            {//缩小，向左

                colIndex--;
            }
            else if (matrix[rowIndex][colIndex] < target)
            {//增大，向下
                rowIndex++;
            }
            else { return true; }
        }
       

return false;

    }
    }
class Program240
{



    static void Main240(string[] args)
    {
        Solution240 solution = new Solution240();
        int[][] matrix = [[1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24],
            [18, 21, 23, 26, 30]];
        int target = 5;
       bool res= solution.SearchMatrix(matrix, target);
        Console.WriteLine(res);
    }
}